Binary Tree Right Side View

LC 199

• 類別：BFS / Level Order Traversal
• 給一棵二元樹，從右側看過去時，可以看到哪些節點？
• 請回傳「從右邊看到的節點值」列表。
• Ex.

Input: 
    1
   / \
  2   3
   \   \
    5   4
Output: [1,3,4]

thoughts

• 使用 BFS 層序遍歷：
• 每層只取「最後一個節點」即可（即該層最右邊）。
• 時間：O(n)
• 空間：O(n)

Kotlin

data class TreeNode(var `val`: Int, var left: TreeNode? = null, var right: TreeNode? = null)

fun rightSideView(root: TreeNode?): List<Int> {
    if (root == null) return emptyList()
    val queue: ArrayDeque<TreeNode> = ArrayDeque()
    val result = mutableListOf<Int>()
    queue.add(root)

    while (queue.isNotEmpty()) {
        val size = queue.size
        for (i in 0 until size) {
            val node = queue.removeFirst()
            if (i == size - 1) result.add(node.`val`) // 最右邊
            node.left?.let { queue.add(it) }
            node.right?.let { queue.add(it) }
        }
    }
    return result
}

Follow-up

• 如何用 DFS（右優先遍歷）實作？
• 如果要取得「左視圖 (Left Side View)」怎麼改？
• 如果樹非常大（例如 100 萬節點），如何減少記憶體使用？